package com.utils;

public class MyMapList {

    //存放地图点对象
    private Map[] maps;
    //实际存储量
    private int size;
    //集合是否有序
    private boolean isSort;

    /**
     * 构造函数
     * @param capacity 集合的初始容量
     */
    public MyMapList(int capacity) {
        this.maps=new Map[capacity];
        this.size=0;
        this.isSort=false;
    }

    /**
     * 对数组进行扩容
     */
    private void resize(){
        if(this.size>=maps.length){
            Map[] newMap=new Map[maps.length*2];
            System.arraycopy(maps,0,newMap,0,maps.length);
            this.maps=newMap;
        }
    }

    /**
     * 根据索引获取集合的元素
     * @param index 索引
     * @return Map对象
     */
    public Map get(int index){
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException("下标越界！");
        return maps[index];
    }

    /**
     * 获取集合长度
     * @return 集合长度
     */
    public int size(){
        return this.size;
    }


    /**
     * 插入元素
     * @param ele 要插入的元素
     * @param index 插入的位置
     */
    public void insert(Map ele,int index) throws IndexOutOfBoundsException{
        if(index<0||index>=maps.length)
        {
            throw new IndexOutOfBoundsException("索引超出数组范围！");
        }
        //判断数组的实际容量和物理容量是否达到上限
        if(size>=maps.length)
            resize();//对数组进行扩容

        for (int i = size-1; i >= index;i--) {
            maps[i+1]=maps[i];
        }
        maps[index]=ele;
        size++;
    }


    /**
     *  根据索引删除元素
     * @param index
     * @throws IndexOutOfBoundsException
     */
    public void deleteEleByIndex(int index) throws IndexOutOfBoundsException{
        if(index < 0 || index >= maps.length){
            throw new IndexOutOfBoundsException("索引超出数组范围！");
        }
        for (int i = index; i < size; i++) {
            maps[i] = maps[i+1];
        }
        size--;
    }

    /**
     * 更改元素，
     * @param temp
     * @param index
     * @throws IndexOutOfBoundsException
     */
    public void update(Map temp,int index) throws IndexOutOfBoundsException {
        if (index < 0 || index >= maps.length) {
            throw new IndexOutOfBoundsException("索引超出数组范围！");
        }
        maps[index] = temp;
    }



    /**
     * 在集合的末尾添加元素
     * @param map
     */
    public void add(Map map){
        if(this.size>=maps.length)
            resize();
        maps[size++]=map;
    }


    /**
     * 冒泡排序
     */
    public void bubbleSort(){
        if(isSort)
            return;
        //外循环 0 size-1
        for (int i = 0; i <size-1 ; i++) {
            //内循环 0  size-1-i
            for (int j = 0; j <size-1-i ; j++) {
                //比较  j
                if(maps[j].getLinkID()>maps[j+1].getLinkID()){
                    //交换
                    Map temp=maps[j];
                    maps[j]=maps[j+1];
                    maps[j+1]=temp;
                }
            }
        }
        isSort=true;//true 表示数组已排序
    }


    /**
     * 根据id查找元素
     * @param id id
     * @return Map对象
     */
    public Map searchById(int id){
        for (int i = 0; i <size ; i++)
            if(maps[i].getLinkID()==id)
                return maps[i];

        return  null;
    }

    /**
     * 根据id查找元素，返回下标index
     * @param id id
     * @return Map对象
     */
    public int getIndexById(int id){
        for (int index = 0; index <size ; index++)
            if(maps[index].getLinkID() == id)
                return index;

        return  -1;
    }


    /**
     * 根据LinkID更改数据
     * @param id
     * @param updateMap
     * @return
     */
    public Map updateById(int id , Map updateMap){
        int i;
        for ( i = 0; i < size; i++ ){
            if (maps[i].getLinkID() == id )
            {
                maps[i] = updateMap;
                return maps[i];
            }
        }
        return null;

    }





    /**
     * 二分查找法或折半查找法
     * 非递归法
     * @return
     */
    public Map binarySearch(int id) throws Exception {
        if(isSort)
            throw new Exception("集合不是有序的！");

        int low=0;
        int high=size-1;
        int mid;
        while (low<=high){
            mid=(low+high)/2;
            if(id==maps[mid].getLinkID()){
                return maps[mid];
            }
            else if(id<maps[mid].getLinkID()){
                high=mid-1;//在左侧册
            }else
                low=mid+1;
        }
        return null;
    }

    /**
     * 二分查找法或折半查找法
     * 递归查找
     * @param id
     * @return
     */
    public Map binarySearch(int id,int low,int high) throws Exception {
        if(isSort)
            throw new Exception("集合不是有序的！");

        if(id<maps[low].getLinkID()||id>maps[high].getLinkID()
                ||low>high)
            return null;

        int mid=(low+high)/2; //算出中间值
        if(maps[mid].getLinkID()==id)
            return maps[mid];
        else if(maps[mid].getLinkID()>id){
            return binarySearch(id,low,mid-1);
        }else
            return binarySearch(id,mid+1,high);

    }

    /**
     * 快速排序入口
     */
    public void quickSort(){
        quickSort(0,size-1);
    }


    private void quickSort(int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(left, right);
            quickSort(left, dp - 1);
            quickSort(dp + 1, right);
        }
    }

    private int partition( int left, int right) {
        Map pivot = maps[left];
        //左右标志位没有重回
        while (left < right) {
            //  左右标志没重合  且 右标识位指向的数大于等于 pivot 继续从右向左推进
            while (left < right && maps[right].getLinkID() >= pivot.getLinkID())
                right--;

            if (left < right)
                maps[left++] = maps[right];

            //  左右标志没重合  且 左标识位指向的数小于等于 pivot 继续从左向右推进
            while (left < right && maps[left].getLinkID() <= pivot.getLinkID())
                left++;

            if (left < right)
                maps[right--] = maps[left];
        }
        maps[left] = pivot;
        return left;
    }

}
